#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v, vv;//v模拟栈，vv有序存储和删除数据
vector<int>::iterator it;

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        string opr;
        cin >> opr;
        if (opr[1] == 'o')
        {
            if (!v.size())
            {
                cout << "Invalid" << endl;
            }
            else
            {
                cout << v.back() << endl;
                it = lower_bound(vv.begin(), vv.end(), v.back());
                vv.erase(it);
                v.pop_back();
            }
        }
        else if (opr[1] == 'e')
        {
            if (!v.size())
            {
                cout << "Invalid" << endl;
            }
            else
            {
                cout << vv[(vv.size() + vv.size() % 2) / 2 - 1] << endl;
            }
        }
        else
        {
            int val;
            cin >> val;
            v.push_back(val);
            it = lower_bound(vv.begin(), vv.end(), val);
            vv.insert(it, val);
        }
    }
    return 0;
}

// 使用手写栈，并不能优化时间

// #include <iostream>
// #include <algorithm>
// #include <string.h>
// using namespace std;

// const int N = 100010;

// int st[N];
// int arr[N];

// int main()
// {
//     ios::sync_with_stdio(false);
//     cin.tie(0), cout.tie(0);
//     int n;
//     cin >> n;
//     while (n--)
//     {
//         string opr;
//         cin >> opr;
//         if (opr[1] == 'o')
//         {
//             if (*st)
//             {
//                 cout << st[*st] << endl;
//                 --*st;
//             }
//             else
//             {
//                 cout << "Invalid" << endl;
//             }
//         }
//         else if (opr[1] == 'e')
//         {
//             if (*st)
//             {
//                 memcpy(arr, st + 1, (*st) * sizeof(int));
//                 sort(arr, arr + *st);
//                 cout << arr[(*st + (*st) % 2) / 2 - 1] << endl;
//             }
//             else
//             {
//                 cout << "Invalid" << endl;
//             }
//         }
//         else
//         {
//             int val;
//             cin >> val;
//             st[++*st] = val;
//         }
//     }
//     return 0;
// }